package com.rran.study.algorithm.hard.day03;

/**
 * @author yy
 * @Type Solution.java
 * @Desc 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
 * 输入: "aacecaaa"
 * 输出: "aaacecaaa"
 * <p>
 * 输入: "abcd"
 * 输出: "dcbabcd"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020/9/5
 */
public class Solution {

    public static void main(String[] args) {
        String s = "aaba";
        Solution solution = new Solution();
        System.out.println(solution.shortestPalindrome(s));
        ;
    }

    public String shortestPalindrome(String s) {
        int length = s.length();
        String reverseStr = convert(s);
        for (int i = 0; i < s.length(); i++) {
            String subS = s.substring(length - i);
            String comS = s.substring(0, length - i);
            String subR = reverseStr.substring(0, i);
            String comR = reverseStr.substring(i, length);
            if (comS.equals(comR)) {
                return subR + comS + subS;
            }
        }
        return "";
    }

    public String convert(String s) {
        StringBuffer sb = new StringBuffer(s);
        return sb.reverse().toString();
    }
}
